P4358 [CQOI2016]密钥破解

这道题没有想象中的那么难，只不过板子P4718 【模板】Pollard-Rho算法是黑的（为什么这道题是紫的）

既然题目保证$n$为两质数$p,q$乘积。我们可以用
$Pollard~Rho$求出$p,q$。

然后跟着题目一步步模拟，计算$r=(p-1)*(q-1)$

然后根据$ed≡1(mod~r)$计算$d$（我用的扩欧）。

最后，用快速幂求出$n≡c^d(mod~N)$

因为数据范围很大，我用的是__int128，注意它不能用标准输入输出，要手写读优输优。

#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
#define int __int128

void Read( int &x ) {
	x = 0;int f = 1;
	char s = getchar( );
	while( s < '0' || s > '9' ) {
		if( s == '-' ) f = -1;
		s = getchar( );
	}
	while( '0' <= s && s <= '9' ) {
		x = x * 10 + s - '0';
		s = getchar( );
	}
	x *= f;
}
void Write( int x ) {
	if( x < 0 ) {
		x = -x;
		putchar('-');
	}
	if( x >= 10 )
		Write( x / 10 );
	putchar( x % 10 + '0' );
}

int Exgcd( int a , int b , int &x , int &y ) {
	if( !b ) {
		x = 1 , y = 0;
		return a;
	}
	else {
		int r = Exgcd( b , a % b , y , x );
		y -= x * ( a / b );
		return r;
	}
}
int Gcd( int x , int y ) {
	return y == 0 ? x : Gcd( y , x % y );
}
int Abs( int x ) {
	return x >= 0 ? x : -x;
}
int f( int x , int a , int Mod ) {
	return ( x * x + a ) % Mod;
}
int Quick_pow( int x , int po , int Mod ) {
	int Ans = 1;
	while( po ) {
		if( po % 2 )
			Ans = Ans * x % Mod;
		x = x * x % Mod;
		po /= 2;
	}
	return Ans;
}
int Inv( int x , int Mod ) {
	int u , v;
	Exgcd( x , Mod , u , v );
	return ( u % Mod + Mod ) % Mod;
}

int Pollard_rho( int n ) {
	int r = rand( ) % ( n - 1 ) + 1;
	int a = f( 0 , r , n ) , b = f( f( 0 , r , n ) , r , n ); 
	while( b != a ) {
		int p = Gcd( Abs( b - a ) , n );
		if( p > 1 ) return p;
		a = f( a , r , n ) , b = f( f( b , r , n ) , r , n );
	}
	return n;
}

int N , e , c , p , q , r , d , n; 
signed main( ) {
	srand( 20060204 );
	
	Read( e ) , Read( N ) , Read( c ); 
	p = Pollard_rho( N ) , q = N / p;
	r = ( p - 1 ) * ( q - 1 );
	d = Inv( e , r );
	n = Quick_pow( c , d , N );
	/*Write( d ) , putchar('\n');
	Write( n ) , putchar('\n');
	Write( p ) , putchar('\n');
	Write( q ) , putchar('\n');
	Write( r ) , putchar('\n'); */
	Write( d ) , putchar(' ') , Write( n ); 
	return 0;
}